package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.*;

/**
 * https://leetcode.cn/problems/course-schedule/description/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 * <p>
 * 拓扑排序
 *
 * @author yulongTian
 * @create 2024-06-28 15:19
 */
public class Test53 {
    public static void main(String[] args) {
//        int[][] prerequisites = {{0, 4}, {0, 1}, {0, 2}, {1, 2}, {2, 3}, {4, 3}};
//        int[][] prerequisites = {{1, 0}, {0, 1}};
        int[][] prerequisites = {{0, 10}, {3, 18}, {5, 5}, {6, 11}, {11, 14}, {13, 1}, {15, 1}, {17, 4}};
//        int numCourses = 5;
//        int numCourses = 2;
        int numCourses = 20;
        System.out.println(new Test53().canFinish(numCourses, prerequisites));
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] dus = new int[numCourses];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            int p = prerequisite[0];
            int q = prerequisite[1];
            dus[q]++;
            if (map.containsKey(p)) {
                map.get(p).add(q);
            } else {
                List<Integer> temp = new ArrayList<>();
                temp.add(q);
                map.put(p, temp);
            }
        }
        int countDus0 = 0;
        Queue<Integer> queueDus0 = new LinkedList<>();
        for (int i = 0; i < dus.length; i++) {
            if (dus[i] == 0) {
                countDus0++;
                queueDus0.add(i);
            }
        }

        while (countDus0 < numCourses) {
            if (queueDus0.size() == 0) {
                return false;
            }
            for (int i = 0; i < queueDus0.size(); i++) {
                int p = queueDus0.poll();
                if (map.containsKey(p)) {
                    List<Integer> list = map.get(p);
                    if (list.size() != 0) {
                        for (Integer q : list) {
                            dus[q]--;
                            if (dus[q] == 0) {
                                countDus0++;
                                queueDus0.add(q);
                            }
                        }
                    }
                }
            }
        }
        return true;
    }

}
